#include <iostream>
#include <queue>
using namespace std;

// 邻接表的边表节点
struct ArcNode {
    int adjvec;      // 邻接点下标（物理索引）
    ArcNode* next;   // 链表指针
    ArcNode(int v) : adjvec(v), next(nullptr) {} // 构造函数
};

// 邻接表的顶点表节点
struct VertexNode {
    int vertex;        // 顶点数据（逻辑值）
    ArcNode* firstEdge;// 边链表头指针
    VertexNode() : vertex(0), firstEdge(nullptr) {} // 初始化
};

class ALGraph {
public:
    ALGraph(int n) : vertexNum(n) {
        adjList = new VertexNode[n]; // 创建顶点数组
        visited = new int[n]();       // 初始化访问标记
    }

    ~ALGraph() {
        // 释放所有边链表节点
        for (int i = 0; i < vertexNum; ++i) {
            ArcNode* p = adjList[i].firstEdge;
            while (p) {
                ArcNode* temp = p;
                p = p->next;
                delete temp; // 逐个删除边节点
            }
        }
        delete[] adjList;  // 释放顶点数组
        delete[] visited;  // 释放访问标记数组
    }

    // 核心功能
    void addEdge(int v1, int v2);
    void DFS();
    void BFS();

    // 设置顶点数据（演示用，实际可根据需求修改）
    void setVertex(int index, int value) {
        if (index >= 0 && index < vertexNum)
            adjList[index].vertex = value;
    }

private:
    // 辅助方法
    void DFSTraverse(int v);
    void resetVisited() { fill(visited, visited + vertexNum, 0); }

    VertexNode* adjList;   // 邻接表主体
    int* visited;          // 访问标记数组
    int vertexNum;         // 顶点总数
};

// 添加无向边（双向）
void ALGraph::addEdge(int v1, int v2) {
    // 头插法添加到v1的边表
    ArcNode* newNode = new ArcNode(v2);
    newNode->next = adjList[v1].firstEdge;
    adjList[v1].firstEdge = newNode;

    // 无向图需对称添加
    newNode = new ArcNode(v1);
    newNode->next = adjList[v2].firstEdge;
    adjList[v2].firstEdge = newNode;
}

// 递归深度优先遍历
void ALGraph::DFSTraverse(int v) {
    visited[v] = 1;
    cout << adjList[v].vertex << " "; // 输出顶点数据
    
    // 遍历邻接点（注意头插法导致逆序访问）
    for (ArcNode* p = adjList[v].firstEdge; p; p = p->next) {
        if (!visited[p->adjvec]) {
            DFSTraverse(p->adjvec);
        }
    }
}

// 完整的DFS遍历（处理非连通图）
void ALGraph::DFS() {
    resetVisited();
    for (int i = 0; i < vertexNum; ++i) {
        if (!visited[i]) {
            DFSTraverse(i);
        }
    }
}

// 广度优先遍历
void ALGraph::BFS() {
    resetVisited();
    queue<int> q;

    for (int i = 0; i < vertexNum; ++i) {
        if (!visited[i]) {
            visited[i] = 1;
            cout << adjList[i].vertex << " ";
            q.push(i);

            while (!q.empty()) {
                int v = q.front();
                q.pop();

                // 访问所有邻接点
                for (ArcNode* p = adjList[v].firstEdge; p; p = p->next) {
                    int neighbor = p->adjvec;
                    if (!visited[neighbor]) {
                        visited[neighbor] = 1;
                        cout << adjList[neighbor].vertex << " ";
                        q.push(neighbor);
                    }
                }
            }
        }
    }
}

// 测试用例
int main() {
    system("chcp 65001"); // 中文编码设置

    /* 构建如下结构的图（物理索引=逻辑值）：
        0
       / \
      1   2
     / \   \
    3  4    5
    */
    ALGraph graph(6);
    for (int i = 0; i < 6; ++i) graph.setVertex(i, i);
    
    graph.addEdge(0, 1);  // 0-1
    graph.addEdge(0, 2);  // 0-2
    graph.addEdge(1, 3);  // 1-3
    graph.addEdge(1, 4);  // 1-4
    graph.addEdge(2, 5);  // 2-5

    cout << "DFS遍历结果（头插法逆序）:\n";
    graph.DFS(); // 输出：0 2 5 1 4 3
    cout << "\n\nBFS遍历结果（层序+头插逆序）:\n";
    graph.BFS(); // 输出：0 2 1 5 4 3
    cout << "\n\n注意：邻接表使用头插法，遍历顺序与边添加顺序相反";

    return 0;
}